﻿<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
	<head>
		<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
		<title>Recherche A*</title>
		<link rel="stylesheet" type="text/css" href="style.css" />
	</head>
	<body class="twoColFixLtHdr">
    <div id="container">
		<div id="header">Algorithme de recherche de chemin A*</div>

		<div id="menu">
			<ul>
				<li><a href="index.html">Accueil</a></li>
				<li><a href="presentation.html">Présentation</a></li>
				<li><a href="connaissances.html">Connaissances</a></li>
				<li><a href="demarche.html">Démarche</a></li>
				<li><a href="difficultes.html">Difficultés</a></li>
				<li><a href="analyse.html">Analyse</a></li>
				<li><a href="conclusion.html">Conclusion</a></li>
				<li><a href="bibliographie.html">Bibliographie</a></li>
				<li><a href="glossaire.html">Glossaire</a></li>
				<li><a href="telechargement.html">Téléchargement</a></li>
			</ul>
		</div>

		<div id="content"><br />
			<a name="top"><h1>Présentation de recherche</h1></a>
			<a href="#sujet">Le sujet</a><br />
			<a href="#enjeu">L'enjeu</a><br />
			<a href="#experi">L'expérimentation</a><br />
			<a href="#ressources">Les ressources</a><br />
			<a href="#limites">Les limites</a><br />
			<br />
			<br />
			<h2><a name="sujet">Le sujet</a></h1>
			Le sujet que nous avons choisi est l'optimisation de l'algorithme de chemin A*. La manière de le prononcer est "A star" puisque le caractère * représente une étoile. Un algorithme de chemin permet de trouver le chemin optimisé pour se rendre d'un point X à un point Y avec des objets entre les deux. Le but de cette recherche est de montrer comment l'agorithme de chemin A* pour être utilisé efficacement dans le contexte d'un RPG, même s'il peut être utilisé dans tous les types de jeux vidéo. Dans notre contexte (les jeux vidéo de nos jours), le monde n'est plus statique. Il y a beaucoup d'objets qui bougent et le monde est énorme. Il est donc nécessaire que l'algorithme de recherche de chemin utilisé soit optimisé pour ne pas faire languir le joueur et qu'il ne passe pas par des chemins trop longs ou erronés. Actuellement, l'A* est principalement utilisé dans les jeux vidéo. Par exemple, il permet à un ennemi de courir après le joueur en empruntant le chemin le plus rapide que possible. L'algorithme de recherche de chemin permet également de faire éviter les obstacles aux personnages sans que l'utilisateur ait explicitement à le faire. Certaines variantes existent également, par exemple le D*, qui est utilisé par des robots de la NASA pour visiter des territoires inconnus et non-cartographiés (comme Mars). En ce début de recherche, nous connaissons le principe général de l'algorithme de base sans les détails de l'implémentation et des optimisations possibles.<br /><br />
			<a href="#top">Retourner en haut</a><br />
			<h2><a name="enjeu">L'enjeu</a></h1>
			La connaissance principale à acquérir dans cette recherche est la capacité à programmer un algorithme d'A*. Nous commencerons avec la version de base où l'algorithme de recherche de chemin fonctionnera dans un monde divisé en cases et il ne sera pas optimisé. Nous voulons par la suite être capable de porter cet algorithme dans un monde où il n'y a pas de case. Finalement, nous optimiserons l'agorithme principalement en réduisant l'aire de recherche, c-a-d en jouant sur la quantité de noeuds. Cette recherche est d'une importance capitale car cet algorithme de recherche de chemin est le plus utilisé dans le domaine de l'IA. Tous les programmeurs qui sont dans ce domaine se doivent d'avoir plus qu'une base. Cette recherche nous permettra de nous initier dans ces concepts de plus en plus en demande. Les impacts majeurs de cette recherche est la capacité à utiliser le A* à l'intérieur d'un jeu sans case et la possibilité d'optmimiser cet algorithme pour faire calculer le chemin en temps réel. Peu importe le jeu, du moment qu'il y a un NPC (Non Player Character) ou qu'il faut trouver un chemin le plus rapide, le A s'impose comme une solution à considérer. Des milliers de jeux ont utilisé cet algorithme parce qu'il est excellent. Le A* sera encore utilisé dans le futur où il sera nécessaire de trouver un chemin optimal qui doit être régulièrement mis à jour sans avoid d'indice. L'A* est un algorithme classique et il est utilisé largement. Nous avons choisi ce sujet parce que l'A* est une solution générique à beaucoup de problèmes dans les jeux vidéo. Nous croyons que pour acquérir une base, nous nous devons d'apprendre le fonctionnement et des manières d'optimiser cet algorithme.<br /><br />
			<a href="#top">Retourner en haut</a><br />

			<h2><a name="experi">L'expérimentation</a></h1>
			L’expérimentation s’est séparée en deux parties. La première partie a été une version console où l’on expérimente le A* de base avec un monde séparé par des cases. Par la suite, nous avons expérimenté le A* dans une fenêtre Windows sans séparation par case.
			<h3>A* de base</h3>
			Pour tester le A* de base, nous avons créé un labyrinthe chargé à partir d’un fichier ASCII. Le S représente le joueur et le E l’endroit où nous voulons nous rendre. Le A* calcul le chemin optimal et l’indique avec des points.
			<h3>A* Windows</h3>
			En transférant l’A* dans une fenêtre Windows, nous perdons la séparation du monde en cases. La manière que l’on a trouvé de se débarrasser de ce concept est en créant un éditeur pour permettre au créateur de la carte de placer des nœuds à des endroits stratégiques. En faisant des recherches, nous n’avons pas trouvé d’autres moyens.<br /><br />
			<a href="#top">Retourner en haut</a><br />

			<h2><a name="ressources">Les ressources</a></h1>
			Voir la <a href="bibliographie.html">bibliographie</a><br />
			<br />
			<a href="#top">Retourner en haut</a><br />

			<h2><a name="limites">Les limites</a></h1>
			Il y a certains éléments que nous aurions pu faire que nous avons délaissés. Tout d'abord, l'exploration d'un terrain inconnu avec l'algorithme inspiré d'A* appelé le D*. On a également décidé de ne pas faire un jeu avec un grand monde et beaucoup d'unités pour mettre à l'épreuve l'optimisation. Nous avons également décidé de ne pas entrer dans le sujet du B*, qui est basé sur une construction des noeuds dans un graphique.<br /><br />
			<a href="#top">Retourner en haut</a><br />
		<br class="clearfloat" />
		<div id="footer"><br /><p align="center">Par Benoît Tremblay et François Roseberry</p></div>
    </div>
	</body>
</html>